package org.cy.algorithm.chapter_06;

import org.cy.algorithm.util.AlgorithmUtil;

import java.util.Arrays;
import java.util.Random;

public class Heap {

    public void heapSort(int[] arr) {
        build(arr);
        // 太秒了，A[0,size-1]是大顶堆，A[size,array.length-1]是排好序的大数
        int size = arr.length;
        for (int i = arr.length - 1; i > 0; i--) {
            AlgorithmUtil.swap(arr, 0, i);
            heapify(arr, 0, --size);
        }
    }

    private void build(int[] arr) {
        for (int i = arr.length / 2; i >= 0; i--) {
            // 下沉
            heapify(arr, i, arr.length);
        }
    }

    /**
     * 上浮 TODO
     *
     * @param arr
     * @param i
     */
    public void flow(int[] arr, int i, int size) {
        int parent = (i - 1) / 2;
        if (parent < 0) {
            return;
        }

        int largest = parent;
        int sibling = i % 2 == 1 ? i + 1 : i - 1;
        if (arr[largest] < arr[i]) {
            largest = i;
        }
        if (sibling < size && arr[largest] < arr[sibling]){
            largest = sibling;
        }
        if (largest != i) {
            AlgorithmUtil.swap(arr, i, largest);
            flow(arr, i, size);
        }
    }

    public void heapify(int[] arr, int i, int size) {
        int left = 2 * i + 1;
        int right = 2 * (i + 1);
        int largest = i;
        if (left < size && arr[left] > arr[i]) {
            largest = left;
        }
        if (right < size && arr[right] > arr[largest]) {
            largest = right;
        }
        if (largest != i) {
            AlgorithmUtil.swap(arr, largest, i);
            heapify(arr, largest, size);
        }
    }

    public static void main(String[] args) {
        for (int i = 0; i < 10000; i++) {
            int[] randomArray = AlgorithmUtil.createRandomArray(new Random().nextInt(100));
            int[] heapArr = AlgorithmUtil.copyArray(randomArray);
            int[] systemSort = AlgorithmUtil.copyArray(randomArray);
            Arrays.sort(systemSort);
            new Heap().heapSort(heapArr);
            if (!Arrays.equals(heapArr, systemSort)) {
                System.out.println("Oops");
                return;
            }
        }
        System.out.println("OK");
    }
}
